1577. Так Вы хотите стать 2^n-эром?

У игрока имеется $1, и ему предстоит последовательно ответить на n вопросов. Перед каждым вопросом он может:

· остановить игру и забрать имеющиеся у него деньги.

· ответить на вопрос. При неправильном ответе игрок покидает игру ни с чем. При правильном ответе денежная сумма удваивается, и игра продолжается со следующим вопросом.

После правильного ответа на последний вопрос игрок забирает свои деньги. Цель игрока — максимизировать ожидаемую сумму выигрыша.

На каждый отдельный вопрос игрок отвечает правильно с вероятностью p. Считайте, что p равномерно распределена на отрезке [t; 1].

Вход. Каждая строка является отдельным тестом и содержит два числа: целое n (1 ≤ n ≤ 30) и действительное t (0 ≤ t ≤ 1). Последняя строка содержит два нуля и не обрабатывается.

Выход. Для каждого теста выведите в отдельной строке максимальную ожидаемую сумму выигрыша при оптимальной стратегии игрока. Результат следует выводить с тремя десятичными знаками.

Пример входа	Пример выхода
1 0.5 1 0.3 2 0.6 24 0.25 0 0	1.500 1.357 2.560 230.138

РЕШЕНИЕ

теория вероятности

Анализ алгоритма

Пусть f(n, a) – максимально возможное значение ожидаемого выигрыша, если игроку предстоит ответить на n вопросов, а начальная сумма равна a.

Если n = 0, игрок остается с начальной суммой, то есть f(0, a) = a.

Вероятность правильного ответа равна p, где t £ p £ 1. Если игрок отвечает правильно на первый вопрос, ему остается n – 1 вопросов, а призовая сумма удваивается и становится равной 2a. С вероятностью 1 – p дается неверный ответ, и вся сумма пропадает. Следовательно, ожидаемый выигрыш после первого вопроса равен

p * f(n – 1, 2a) + (1 – p) * 0 = p * f(n – 1, 2a)

Если это значение превышает текущую сумму a, то выгодно продолжить игру; иначе – следует остановиться. Таким образом, ожидаемый выигрыш после решения о продолжении равен

max(a, p * f(n – 1, 2a))

Поскольку вероятность p равномерно распределена на отрезке [t; 1], то

f(n, a) =

Если t = 1, то вероятность правильного ответа равна единице, и тогда игрок должен отвечать на все n вопросов, получая итоговый выигрыш 2ⁿ.

Пример

Рассмотрим третий тест, в котором n = 2, t = 0.6. Начальный капитал a = 1.

f(2, 1) = ,

f(1, 2) = ,

f(0, 4) = 4

Вычислим значение f(1, 2) через f(0, 4):

f(1, 2) = = =

/ учитываем, что 4p > 2 при 0.6 £ p £ 1 /

= =

5 * (1 – 0.36) = 5 * 0.64 = 3.2

Вычислим значение f(2, 1) через f(1, 2):

f(2, 1) = = =

/ учитываем, что 3.2p > 1 при 0.6 £ p £ 1 /

= =

4 * (1 – 0.36) = 4 * 0.64 = 2.56

Реализация алгоритма

Функция integral вычисляет значение интеграла

I(a, k) =

для заданных действительных чисел a и k. При t = 1 вероятность угадывания p равна единице, поэтому значение интеграла I(a, k) полагается равным max(a, k).

Ниже показана область, площадь которой равна значению интеграла :

Найдем точку пересечения прямых y = a и y = kp:

a = kp, откуда p = a/k

Положим temp = a / k. Значение интеграла рассмотрим как сумму + . В зависимости от положения точки temp относительно точек t и 1 вычисляем значение интеграла I(a, k).

· Если t £ temp £ 1, то + =

a * (temp – t) + k * (1 – temp * temp) / 2

· Если temp £ t, то + = = k * (1 – t * t) / 2.

· Если temp > 1, то + = = a * (1 – t).

double integral(double a, double k)

{

double s = 0, temp = a / k;

if (t == 1) return max(a,k);

if (temp > 1) return a * (1 - t);

if (temp >= t) s = a * (temp - t);

else temp = t;

s += k * (1 – temp * temp) / 2;

return s / (1 - t);

}

Фунция f рекурсивно вычисляет значение

f(n, a) =

double f(int n, int a)

{

if (!n) return a;

double k = f(n-1,2*a);

return integral(a,k);

}

Основной цикл программы. Читаем входные данные и выводим значение f(n, 1).

while(scanf("%d %lf",&n,&t),n + t)

printf("%.3lf\n",f(n,1));